摘要 :
Pseudo-boolean (and general nonlinear integer) functions provide an extremely powerful modeling and solution tool in operations research and related areas. A large number of practical as well as purely theoretical decision problem...
展开
Pseudo-boolean (and general nonlinear integer) functions provide an extremely powerful modeling and solution tool in operations research and related areas. A large number of practical as well as purely theoretical decision problems can be easily represented and solved as optimization of a pseudo-boolean or general nonlinear integer function. In the framework of this project we have considered several stochastic extensions of classical combinatorial optimization problems that involve some type of nonlinearity, typically in the objective function. We have provided respective theoretical analysis and developed advanced solution approaches. In particular, we have investigated the following topics: (i) exact solution algorithms for broad classes of two-stage stochastic quadratic binary and general integer programming problems; (ii) approximation algorithms for solving a class of two- stage stochastic assignment problems; (iii) theoretical analysis of two-stage stochastic minimum s-t cut problems; (iv) exact solution algorithm for a class of stochastic bilevel knapsack problems; (v) exact solution algorithms for a class multiple-ratio fractional programming problems; and (vi) integer programming approach for solving a polyomino tiling problem with application in antenna design.
收起
摘要 :
This research considers the optimal allocation of weapons to a collection of targets with the objective of maximizing the value of destroyed targets. The weapon-target assignment (WTA) problem is a classic non-linear combinatorial...
展开
This research considers the optimal allocation of weapons to a collection of targets with the objective of maximizing the value of destroyed targets. The weapon-target assignment (WTA) problem is a classic non-linear combinatorial optimization problem with an extensive history in operations research literature. The dynamic weapon target assignment (DWTA) problem aims to assign weapons optimally over time using the information gained to improve the outcome of their engagements. This research investigates various formulations of the DWTA problem and develops algorithms for their solution. Finally, an embedded optimization problem is introduced in which optimization of the multi-stage DWTA is used to determine optimal weaponeering of aircraft. Approximate dynamic programming is applied to the various formulations of the WTA problem. Like many in the field of combinatorial optimization, the DWTA problem suffers from the curses of dimensionality and exact solutions are often computationally intractability. As such, approximations are developed which exploit the special structure of the problem and allow for efficient convergence to high-quality local optima. Finally, a genetic algorithm solution framework is developed to test the embedded optimization problem for aircraft weaponeering.
收起
摘要 :
The research objectives of this program were: (1) To extend the theory base in nonsmooth analysis; (2) To apply that theory to develop algorithms that extend the range of optimization problems that can be solved; (3) To improve th...
展开
The research objectives of this program were: (1) To extend the theory base in nonsmooth analysis; (2) To apply that theory to develop algorithms that extend the range of optimization problems that can be solved; (3) To improve the understanding of convergence behavior in stochastic optimization; and (4) To apply that understanding to the design and analysis of improved algorithms for solving optimization problems in important application areas such as manufacturing.
收起
摘要 :
In this paper, we propose a stochastic search algorithm for solving general optimization problems with little structure. The algorithm iteratively finds high quality solutions by randomly sampling candidate solutions from a parame...
展开
In this paper, we propose a stochastic search algorithm for solving general optimization problems with little structure. The algorithm iteratively finds high quality solutions by randomly sampling candidate solutions from a parameterized distribution model over the solution space. The basic idea is to convert the original (possibly non-differentiable) problem into a differentiable optimization problem on the parameter space of the parameterized sampling distribution, and then use a direct gradient search method to find improved sampling distributions. Thus, the algorithm combines the robustness feature of stochastic search from considering a population of candidate solutions with the relative fast convergence speed of classical gradient methods by exploiting local differentiable structures. We analyze the convergence and converge rate properties of the proposed algorithm, and carry out numerical study to illustrate its performance.
收起
摘要 :
A stochastic control problem is obtained as a small noise approximation to a deterministic optimal control problem. Two classes of admissible controls are considered and the optimal control policies are explicitly determined for a...
展开
A stochastic control problem is obtained as a small noise approximation to a deterministic optimal control problem. Two classes of admissible controls are considered and the optimal control policies are explicitly determined for a each admissible class. The larger admissible class contains controls referred to as singular stochastic controls. For this class, the cumulative effect of control has bounded variation trajectories. The smaller admissible class contains the standard stochastic controls whose cumulative effect has absolutely continuous trajectories. These controls are referred to as absolutely continuous controls. the optimal singular control provides a cost strictly smaller than the minimum cost achievable when only absolutely continuous stochastic controls are admissible. In particular, this shows that is not always possible to approach the optimal cost for singular control is only the standard stochastic control policies are admissible. Keywords: Hamilton-Jacobi-Bellman equation.
收起
摘要 :
The investigator made progress extending the theory of free boundary control (or singular control) to the multidimensional case. Two papers were submitted for publication: Optimal corrections problem of a multidimensional stochast...
展开
The investigator made progress extending the theory of free boundary control (or singular control) to the multidimensional case. Two papers were submitted for publication: Optimal corrections problem of a multidimensional stochastic system and Deterministic equivalents for a continuous linear-convex stochastic control problem.
收起
摘要 :
Stochastic search and optimization very widely used. This briefing looks at the use of search and optimization algorithms. Looks at examples of uses.
摘要 :
The paper solves the problem of finding the optimal strategy at roulette, where one's object is to attain a fortune 1, given a certain lesser fortune to begin with. The probability of attaining fortune 1, as a function of the star...
展开
The paper solves the problem of finding the optimal strategy at roulette, where one's object is to attain a fortune 1, given a certain lesser fortune to begin with. The probability of attaining fortune 1, as a function of the starting fortune, is an increasing, continuous singular function. (Author)
收起